package com.ggqq.sort;

import java.util.Arrays;

public class Quick {

    public static void main(String[] args) {
        int[] arr = {25,84,21,46,13,27,68,35,20};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int start,int end){
        //分治
        if(start<end){
            int index = getIndex(arr,start,end);  //基准元素
            quickSort(arr,start,index-1);//左区
            quickSort(arr,index+1,end);//右区
        }
    }
    //获取基准元素
    private static int getIndex(int[] arr,int start,int end) {
        int i = start;
        int j = end;
        int x = arr[i];
        while(i<j){
            //由后向前找比他小的数,直到找到暂停
            while(i<j && arr[j]>x){
                j--;
            }
            if(i<j){
                arr[i] = arr[j];//将找到的数挖出来填到前一个坑中
                i++;
            }

            //由前向后找比他大的数,直到找到暂停
            while(i<j && arr[i]<x){
                i++;
            }
            if(i<j){
                arr[j] = arr[i];//将找到的数挖出来填到前一个坑中
                j--;
            }
        }


        //将基准数填到最后的坑中（此时i和j相等）
        arr[i] = x;

        return i;
    }
}
